package leetcode;

public class LeetCode86 {

    public ListNode partition(ListNode head, int x) {
        ListNode smallQueue = new ListNode(-1), smallTail = smallQueue;
        ListNode bigQueue = new ListNode(-1), bigTail = bigQueue;
        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                smallTail.next = p;
                smallTail = smallTail.next;
            } else {
                bigTail.next = p;
                bigTail = bigTail.next;
            }
            p = p.next;
        }
        bigTail.next = null;
        smallTail.next = bigQueue.next;
        return smallQueue.next;
    }
//------------------------------------------------------------------
}
